Counting acyclic hypergraphs

Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. The number of distinct acyclic uniform hypergraphs withn labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicitformula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.     

Neighborhood hypergraphs of bipartite graphs

Matrix symmetrization and several related problems have an extensive literature, with a recurring ambiguity regarding their complexity and relation to graph isomorphism. We present a short survey of these problems to clarify their status. In particular, we recall results from the literature showing that matrix symmetrization is in fact NP‐hard; furthermore, it is equivalent with the problem of recognizing whether a hypergraph can be realized as the neighborhood hypergraph of a graph. There are several variants of the latter problem corresponding to the concepts of open, closed, or mixed neighborhoods. While all these variants are NP‐hard in general, one of them restricted to the bipartite graphs is known to be equivalent with graph isomorphism. Extending this result, we consider several other variants of the bipartite neighborhood recognition problem and show that they all are either polynomial‐time solvable, or equivalent with graph isomorphism. Also, we study uniqueness of neighborhood realizations of hypergraphs and show that, in general, for all variants of the problem, a realization may be not unique. However, we prove uniqueness in two special cases: for the open and closed neighborhood hypergraphs of the bipartite graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 69–95, 2008     

Parallel and fast sequential algorithms for undirected edge connectivity augmentation

1 ,E₂,..., such that ⋃_i≤τE_i optmially increases the connectivity by τ, for any integer τ. The main result of the paper is that this sequence of edge sets can be divided into O(n) groups such that within one group, all E_i are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs. Received November 1995 / Revised version received July 1998 Published online March 16, 1999     

一类超图的异色数

一个超图Ｈ＝（Ｖ，Ｅ）的一个ｔ着色是从Ｖ到一个ｔ元集的满射，称Ｈ的一个ｔ着色ｆ分离Ｈ的一个条边α∈Ｅ（Ｇ）如果｜ｆ（ａ）｜＝｜α｜。称ｆ为异色的如果ｆ分离Ｈ的至和一条边，否则ｆ为非异色。Ｈ的异色数，记为ｈｃ（Ｈ），是最小的数ｔ使得任一个着色都是异色。在本文中，我们引进一类超图，并确定了它们的异色数。     

On Balanced Graphs

Berge defined a hypergraph to be balanced if its incidence matrix is balanced. We consider this concept applied to graphs, and call a graph to be balanced when its clique matrix is balanced. Characterizations of balanced graphs by forbidden subgraphs and by clique subgraphs are proved in this work. Using properties of domination we define four subclasses of balanced graphs. Two of them are characterized by 0–1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the problems of stable set, clique-independent set and clique-transversal for one of these subclasses of balanced graphs. Finally, we analyse the behavior of balanced graphs and these four subclasses under the clique graph operator. Received: April, 2004     

Choosability with Separation of Complete Multipartite Graphs and Hypergraphs

For a hypergraph G and a positive integer s, let be the minimum value of l such that G is L‐colorable from every list L with for each and for all . This parameter was studied by Kratochvíl, Tuza, and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of for balanced complete multipartite graphs and for complete k‐partite k‐uniform hypergraphs.     

On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that      

Embedding Factorizations for 3‐Uniform Hypergraphs

In this article, two results are obtained on a hypergraph embedding problem. The proof technique is itself of interest, being the first time amalgamations have been used to address the embedding of hypergraphs. The first result finds necessary and sufficient conditions for the embedding a hyperedge‐colored copy of the complete 3‐uniform hypergraph of order m, , into an r‐factorization of , providing that . The second result finds necessary and sufficient conditions for an embedding when not only are the colors of the hyperedges of given, but also the colors of all the “pieces” of hyperedges on these m vertices are prescribed (the “pieces” of hyperedges are eventually extended to hyperedges of size 3 in by adding new vertices to the hyperedges of size 1 and 2 during the embedding process). Both these results make progress toward settling an old question of Cameron on completing partial 1‐factorizations of hypergraphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 216–224, 2013